#define _CRT_SECURE_NO_WARNINGS 1

#include<iostream>
#include<vector>

using namespace std;

int maxSubArr(vector<int>& arr, int k)
{
    int n = arr.size();
    int res = 0, f = 0;
    for (int i = 0; i < n * k; i++)
    {
        f = max(f, 0) + arr[i % n];
        res = max(res, f);
    }
    return res;
}

int kConcatenationMaxSum(vector<int>& arr, int k) {
    if (k == 1)  return maxSubArr(arr, 1);
    const int mod = 1e9 + 7;
    long long res = maxSubArr(arr, 2);
    int sum = reduce(arr.begin(), arr.end());
    res += 1LL * max(sum, 0) * (k - 2);
    return res % mod;
}